package algorithm.dynamic_planning.leetcode;

import java.util.Map;

/**
 * @author yuisama
 * @date 2022年12月01日 21:57
 * @description 基本打家劫舍，相邻房屋不能偷
 */
public class Num198_RobBase {
    /**
     * f(n) = f(n-1) + f(n-2)
     * f(n-1) 即偷前n-1个房子，第n个房子不偷
     * f(n-2),即偷前n-2个房子，第n个房子偷
     * 原问题即可转换为这两个子问题的解，即到底偷不偷最后一间房子的问题
     * dp[n] = dp[n-1] + dp[n-2]
     * =>
     * dp[n] = Math.max(dp[n-1],(dp[n-2] + H[n]))
     * dp[0] = 0;
     * dp[1] = H[1]
     * H[i] = nums[i - 1]
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        int[] dp = new int[nums.length + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= nums.length; i++) {
            dp[i] = Math.max(dp[i - 1],(dp[i - 2] + nums[i - 1]));
        }
        return dp[nums.length];
    }
}
